package com.dcsgo.quickSort;

import java.util.Arrays;

public class QuickSort {
    //arr数组以target划分成两部分 左大 右小
    public static int partition(int[] arr, int left, int right) {
        int target = arr[left];
        int targetIndex = left;
        while (left < right) {
            //先从右边找小 2 6 5 4 |3
            while (left < right && target <= arr[right]) {
                right--;
            }
            arr[targetIndex] = arr[right];
            targetIndex = right;
            //再从左边找大 2 3 4 |3
            while (left < right && target >= arr[left]) {
                left++;
            }
            arr[targetIndex] = arr[left];
            targetIndex = left;
        }
        arr[targetIndex] = target;
        return targetIndex;
    }

    public static void quickSort(int[] arr, int left, int right) {
        if (left >= right) {
            return;
        }
        int mid = partition(arr, left, right);
        quickSort(arr, left, mid - 1);
        quickSort(arr, mid + 1, right);
    }

    public static void main(String[] args) {
        int[] num = {10, 3, 5, 7, 2, 4, 6, 8, 1, 9};
        quickSort(num, 0, num.length - 1);
        System.out.println(Arrays.toString(num));
    }
}
